package arithmeticSortList;

/**
 * 排序 http://www.jianshu.com/p/8c915179fd02
 * https://git.oschina.net/GggggitHub/MyJava.git
 * 
 * @author jie
 * 
 */
public class EightBase {
	private static int[] abc = { 92, 32, 121, 23, 34, 67, 45, 234, 56, 34, 21,
			34, 67, 8, 55 };

	public static void main(String[] args) {
		int[] abc = { 92, 32, 32,23,121, 23, 34, 67, 45, 234, 8 };
		// bubbleSort(abc);
		 quick(abc);
		// selectSort(abc);
		// insertSort(abc);
//		shellSort(abc);
		for (int i : abc) {
			System.out.print(i + ",");
		}
	}

	// I 冒泡
	/*
	 * 冒泡排序 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
	 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。
	 * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
	 * 
	 * @param numbers 需要排序的整型数组
	 * 
	 * 冒泡排序还可以再优化一下。添加一个上次是否有交换的标识位，如果没有，直接跳出第一层for循环。
	 */
	public static void bubbleSort(int[] numbers) {
		int temp = 0;
		for (int i = 0; i < numbers.length - 1; i++) {
			for (int j = 0; j < numbers.length - 1 - i; j++) {
				if (numbers[j] > numbers[j + 1]) {
					temp = numbers[j];
					numbers[j] = numbers[j + 1];
					numbers[j + 1] = temp;
				}
			}
		}
	}

	// II 快速排序的基本思想：
	// 通过一趟排序将待排序记录分割成独立的两部分，
	// 其中一部分记录的关键字均比另一部分关键字小，
	// 则分别对这两部分继续进行排序，直到整个序列有序。
	// 分析：
	// 　快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。
	// 但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。
	// 为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。
	// 快速排序是一个不稳定的排序方法。

	/**
	 * II 1.查找中轴（最低位作为中轴）所在位置： 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
	 * @see{rankDemo.QuickSortDemo2#getMiddle(int[], int, int)}
	 * 
	 * @param numbers
	 *            带查找数组
	 * @param low
	 *            开始位置
	 * @param high
	 *            结束位置
	 * @return 中轴所在位置
	 */
	public static int getMiddle(int[] numbers, int low, int high) {
		int temp = numbers[low]; // 数组的第一个作为中轴
		while (low < high) {
			while (low < high && numbers[high] >= temp) {
				high--;
			}
			numbers[low] = numbers[high];// 比中轴小的记录移到低端
			while (low < high && numbers[low] < temp) {
				low++;
			}
			numbers[high] = numbers[low]; // 比中轴大的记录移到高端
		}
		numbers[low] = temp; // 中轴记录到尾
		return low; // 返回中轴的位置
	}

	/**
	 * II 2、 递归形式的分治排序算法：
	 * 
	 * 基本思想：自己调用自己 结构：
	 * 
	 * 递归头：定义递归结束的时候，什么时候不调用自身方法。如果没有定义头，将会陷入死循环
	 * 
	 * 递归体：什么时候需要调用自身方法
	 * 
	 * @param numbers
	 *            带排序数组
	 * @param low
	 *            开始位置
	 * @param high
	 *            结束位置
	 */
	public static void quickSort(int[] numbers, int low, int high) {
		if (low < high) {
			int middle = getMiddle(numbers, low, high); // 将numbers数组进行一分为二
			quickSort(numbers, low, middle - 1); // 对低字段表进行递归排序
			quickSort(numbers, middle + 1, high); // 对高字段表进行递归排序
		}

	}

	/**
	 * II 3、快速排序提供方法调用： 快速排序
	 * 
	 * @param numbers
	 *            带排序数组
	 */
	public static void quick(int[] numbers) {
		if (numbers.length > 0) // 查看数组是否为空
		{
			quickSort(numbers, 0, numbers.length - 1);
		}
	}

	// III 选择排序
	/**
	 * 选择排序算法 在未排序序列中找到最小元素， 存放到排序序列的起始位置 再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。
	 * 以此类推，直到所有元素均排序完毕。
	 * 
	 * @param numbers
	 */
	public static void selectSort(int[] numbers) {
		int temp = 0;// 中间变量
		for (int i = 0; i < numbers.length - 1; i++) {
			int k = i;// 待确定的位置
			// 选择出应该在第i个位置的数
			for (int j = i; j < numbers.length - 1; j++) {
				if (numbers[k] > numbers[j + 1]) {
					k = j + 1;
				}
			}
			// 交换两个数
			temp = numbers[i];
			numbers[i] = numbers[k];
			numbers[k] = temp;
		}
	}

	// 　IV　插入排序
	// 基本思想：每步将一个待排序的记录，
	// 按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后）
	// ，直到全部插入排序完为止。
	/**
	 * 插入排序
	 * 
	 * 从第一个元素开始，该元素可以认为已经被排序 取出下一个元素，在已经排序的元素序列中从后向前扫描
	 * 如果该元素（已排序）大于新元素，将该元素移到下一位置 重复步骤3， 直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置中
	 * 重复步骤2
	 * 
	 * @param numbers
	 *            待排序数组
	 */
	public static void insertSort(int[] numbers) {
		int size = numbers.length;
		int temp = 0;
		int j = 0;

		for (int i = 0; i < size; i++) {
			temp = numbers[i];
			// 假如temp比前面的值小，则将前面的值后移 整体移位和冒泡差不多
			for (j = i; j > 0 && temp < numbers[j - 1]; j--) {
				numbers[j] = numbers[j - 1];
			}
			// 将 temp 替换到 目标位置
			numbers[j] = temp;
		}
	}

	// V
	/**
	 * 基本思想： 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
	 * 希尔排序的原理:根据需求，如果你想要结果从大到小排列，它会首先将数组进行分组，然后将较大值移到前面，较小值
	 * 移到后面，最后将整个数组进行插入排序，这样比起一开始就用插入排序减少了数据交换和移动的次数，可以说希尔排序是加强 版的插入排序 拿数组5, 2,
	 * 8, 9, 1, 3，4来说，数组长度为7，当increment为3时，数组分为两个序列
	 * 5，2，8和9，1，3，4，第一次排序，9和5比较，1和2比较，3和8比较，4和比其下标值小increment的数组值相比较
	 * 此例子是按照从大到小排列，所以大的会排在前面，第一次排序后数组为9, 2, 8, 5, 1, 3，4
	 * 第一次后increment的值变为3/2=1,此时对数组进行插入排序， 实现数组从大到小排
	 */
	public static void shellSort(int[] data) {
		int j = 0;
		int temp = 0;
		// 每次将步长缩短为原来的一半
		for (int increment = data.length / 2; increment > 0; increment /= 2) {
			for (int i = increment; i < data.length; i++) {
				temp = data[i];
				for (j = i; j >= increment; j -= increment) {
					System.out.println(i + "  " + increment + "  " + j + ","
							+ (j - increment));
					if (temp < data[j - increment])// 如想从小到大排只需修改这里
					{
						data[j] = data[j - increment];
					} else {
						break;
					}

				}
				data[j] = temp;
			}

		}
	}
}
